module LogiLang.Match (
	match,
	unify )
	where

import LogiLang.Environment

match :: Environment -> Pattern -> Pattern -> Maybe Environment
match env (Variable ident) datum =
	if consistent
		then Just $ insertVar env ident datum
		else Nothing
	where
	consistent =
		case lookupId env ident of
			Nothing -> True
			Just oldvalue -> oldvalue == datum 

match env (Singleton pat) (Singleton str) 
	| str == pat = Just env 
	| otherwise = Nothing

match env (Combination (DottedTail ident : [])) datum@(Combination _) =
	match env (Variable ident) datum

match env (Combination []) (Combination []) = Just env
match env (Combination (pat:rest)) (Combination (hd:tl)) =
	case match env pat hd of
		Nothing -> Nothing
		Just env' ->
		   match env' (Combination rest) (Combination tl) 

match _ _ (Variable _) = error "Cannot match datum with variables" 
match _ _ (DottedTail _) = error "Cannot match datum with dotted tails"
		
match _ _ _ = Nothing

unify :: Environment -> Pattern -> Pattern -> Maybe Environment
unify env (Singleton left) (Singleton right)
	| left == right = Just env
	| otherwise = Nothing

unify env (Variable identl) value@(Variable identr) = 
	case lookupId env identl of
		Just oldvalue -> unify env oldvalue value
		Nothing ->
			case lookupId env identr of
				Just rvalue -> unify env rvalue value
				Nothing ->
					if occursCheck env identl value
						then Nothing
						else Just $ insertVar env identl value


unify env (Variable ident) value = 
	case lookupId env ident of
		Just oldvalue -> unify env oldvalue value
		Nothing ->
			if occursCheck env ident value
				then Nothing
				else Just $ insertVar env ident value 

unify env value var@(Variable _) =
	unify env var value

unify env (Combination []) (Combination []) = Just env
unify env (Combination (DottedTail identl : [])) (Combination (DottedTail identr : [])) =
	unify env (Variable identl) (Variable identr)

unify env (Combination (DottedTail ident : [])) val@(Combination _) =
	unify env (Variable ident) val

unify env val@(Combination _) (Combination (DottedTail ident : [])) =
	unify env (Variable ident) val

unify env (Combination (lh:lt)) (Combination (rh:rt)) =
	case unify env lh rh of
		Nothing -> Nothing
		Just env' -> unify env'  (Combination lt) (Combination rt)

unify _ _ _ = Nothing

occursCheck :: Environment -> Identifier -> Pattern -> Bool
occursCheck _ _ (Singleton _) = False
occursCheck env ident (Combination children) = 
	foldl (||) False (map (occursCheck env ident) children)
occursCheck env ident (Variable var) =
	if ident == var
		then True
		else
			case lookupId env var of
				Nothing -> False
				Just val -> occursCheck env ident val

occursCheck env ident (DottedTail var) =
	occursCheck env ident (Variable var)

